// https://www.lintcode.com/problem/set-matrix-zeroes/

public class Solution {
    /**
     * @param matrix: A lsit of lists of integers
     * @return: nothing
     */
    public void setZeroes(int[][] matrix) {
        // write your code here
        int rows = matrix.length;
        if (rows == 0) {
          return;
        }
        int cols = matrix[0].length;
        boolean zfr = false; // 第一行是否需要清零
        boolean zfc = false; // 第一列是否需要清零
        for (int c = 0; c < cols; ++c) {
          if (matrix[0][c] == 0) {
            zfr = true;
            break;
          }
        }
        for (int r = 0; r < rows; ++r) {
          if (matrix[r][0] == 0) {
            zfc = true;
            break;
          }
        }
        // 使用第一行和第一列做为清零标记位
        for (int r = 1; r < rows; ++r) {
          for (int c = 1; c < cols; ++c) {
            if (matrix[r][c] == 0) {
              System.out.println(r + ", " + c);
              matrix[0][c] = 0;
              matrix[r][0] = 0;
            }
          }
        }
        for (int r = 1; r < rows; ++r) {
          if (matrix[r][0] == 0) {
            zeroRow(matrix, r);
          }
        }
        for (int c = 1; c < cols; ++c) {
          if (matrix[0][c] == 0) {
            zeroCol(matrix, c);
          }
        }
        if (zfr) {
          zeroRow(matrix, 0);
        }
        if (zfc) {
          zeroCol(matrix, 0);
        }
    }

    protected void zeroRow(int[][] matrix, int row) {
      Arrays.fill(matrix[row], 0);
    }

    protected void zeroCol(int[][] matrix, int col) {
      for (int r = 0; r < matrix.length; ++r) {
        matrix[r][col] = 0;
      }
    }
}